#define _CRT_SECURE_NO_WARNINGS
#include"sort.h"
#include"stack.h"

void tmp(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

int mid(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (left > mid)
	{
		if (mid > right)
		{
			return mid;
		}
		else
		{
			if (left > right)
			{
				return right;
			}
			else
			{
				return left;
			}
		}
	}
	else
	{
		if (left > right)
		{
			return left;
		}
		else
		{
			if (mid > right)
			{
				return right;
			}
			else
			{
				return mid;
			}
		}
	}
}

void InsertSort(int* arr, int n)
{
	for (int i = 1; i < n; i++)
	{
		int cur = arr[i];
		int tmp = i-1;
		while (tmp >= 0)
		{
			if (cur < arr[tmp])
			{
				arr[tmp + 1] = arr[tmp];
				tmp--;
			}
			else
			{
				break;
			}
		}
		arr[tmp + 1] = cur;
	}
}

void QueckSort(int* arr, int begin, int end)
{
	if (begin >= end)return;
	if (end - begin + 1 <= 10)InsertSort(arr + begin, end - begin + 1);
	int prev = begin;
	int cur = prev + 1;
	tmp(&arr[mid(arr, begin, end)], &arr[begin]);
	int keyi = begin;
	while (cur <= end)
	{
		if (arr[cur] < arr[keyi])
		{
			tmp(&arr[++prev], &arr[cur]);
		}
		cur++;
	}
	tmp(&arr[prev], &arr[keyi]);
	QueckSort(arr, begin, prev - 1);
	QueckSort(arr, prev + 1, end);
}

void MergeSort_(int* arr,int* tmp, int begin, int end)
{
	if (begin >= end)return;
	int mid = (begin + end) / 2;
	MergeSort_(arr, tmp, begin, mid);
	MergeSort_(arr, tmp, mid + 1, end);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while(begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	memmove(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		return;
	}
	UnMergeSort_(arr, tmp, 0, n - 1);
}

void UnQueckSort(int* arr, int begin, int end)
{
	stack list;
	StackInit(&list);
	StackPush(&list, end);
	StackPush(&list, begin);
	while (!StackEmpty(&list))
	{
		int begin1 = StackTop(&list);
		StackPop(&list);
		int end1 = StackTop(&list);
		StackPop(&list);

		int prev = begin1;
		int cur = prev + 1;
		tmp(&arr[mid(arr, begin1, end1)], &arr[begin1]);
		int keyi = begin1;
		while (cur <= end1)
		{
			if (arr[cur] < arr[keyi])
			{
				tmp(&arr[++prev], &arr[cur]);
			}
			cur++;
		}
		tmp(&arr[prev], &arr[keyi]);

		if (end1 - prev + 1 > 1)
		{
			StackPush(&list, end1);
			StackPush(&list, prev + 1);
		}
		if (prev - begin1 > 1)
		{
			StackPush(&list, prev);
			StackPush(&list, begin1);
		}
	}





	StackDestroy(&list);
}

void UnMergeSort_(int* arr, int* tmp, int begin, int end)
{
	int gap = 1;
	while (gap < end - begin + 1)
	{
		for (int j = 0; j < end - begin + 1; j += 2*gap)
		{
			int begin1 = j, end1 = begin1 + gap - 1;
			int begin2 = j + gap, end2 = begin2 + gap - 1;
			if (end1 >= end - begin + 1 || begin2 >= end - begin + 1)
			{
				break;
			}
			else if(end2>=end-begin+1)
			{
				end2 = end - begin;
			}
			printf("[%d,%d][%d,%d]", begin1, end1, begin2, end2);

			int i = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[i++] = arr[begin1++];
				}
				else
				{
					tmp[i++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[i++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[i++] = arr[begin2++];
			}
			memmove(arr + j, tmp + j, sizeof(int) * (2*gap));
		}
		gap *= 2;
		printf("\n");
	}
}